bzoj 1924 [Sdoi2010]所驼门王的宝藏 发表于 2018-02-02 | 分类于 题解 , bzoj | bzoj1924 tarjan后dp常规操作求最长路 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113#include<cstdio>#include<iostream>#include<algorithm>#include<map>#define LL long longconst int maxn = 5000007;inline int read(){ int x=0,f=1; char c=getchar(); while(c<'0' || c>'9') {if (c=='-') f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}struct data{ int x,y,id,opt;}a[maxn];struct edge{ int to,next;}edge[maxn<<2],E[maxn];int head[maxn],H[maxn>>1],cnt,recnt,ind,top,n,x,y;bool inq[maxn],vis[maxn>>1];int ans; int q[maxn],dfn[maxn],low[maxn];int size[maxn>>1],belong[maxn],tot;bool cmp_x(data a,data b) { return a.x<b.x;}bool cmp_y(data a,data b) { return a.y<b.y;}void add_edge(int x, int y) { edge[++cnt].to=y; edge[cnt].next=head[x]; head[x]=cnt;}void Add_edge(int x, int y) { E[++recnt].to=y; E[recnt].next=H[x]; H[x]=recnt;}void tarjan(int x) { q[++top]=x; dfn[x]=low[x]=++ind; inq[x]=1; for(int i=head[x];i;i=edge[i].next) if(!dfn[edge[i].to]) { tarjan(edge[i].to); low[x]=std::min(low[x],low[edge[i].to]); } else if (inq[edge[i].to]) low[x]=std::min(low[x],dfn[edge[i].to]); int now=-1; if(dfn[x]==low[x]) { tot++; while(now!=x) { now=q[top--]; belong[now]=tot; size[tot]++; inq[now]=0; } }}void dfs(int x) { vis[x]=1;int mx=0; for(int i=H[x];i;i=E[i].next){ if(!vis[E[i].to]) dfs(E[i].to); mx=std::max(size[E[i].to],mx); } ans=std::max(ans,size[x]+=mx);}std::map<LL,int>GG;int main() { n=read();x=read();y=read(); for (int i=1; i<=n; i++) a[i].x=read(), a[i].y=read(),a[i].opt=read(),GG[(LL)a[i].x*maxn+a[i].y]=i,a[i].id=i; std::sort(a+1,a+n+1,cmp_x); for(int i=1;i<=n;i++) if(a[i].opt==1) { for (int j=i-1;j>=1; j--) if (a[i].x==a[j].x) add_edge(a[i].id,a[j].id); else break; for (int j=i+1; j<=n; j++) if (a[i].x==a[j].x) add_edge(a[i].id,a[j].id); else break; } std::sort(a+1,a+n+1,cmp_y); for(int i=1;i<=n;i++) if(a[i].opt==2) { for(int j=i-1;j>=1;j--) if(a[i].y==a[j].y) add_edge(a[i].id,a[j].id); else break; for(int j=i+1;j<=n;j++) if(a[i].y==a[j].y) add_edge(a[i].id,a[j].id); else break; } for(int i=1;i<=n;i++) if(a[i].opt==3){ for(int j=a[i].x-1; j<=a[i].x+1; j++) for(int k=a[i].y-1; k<=a[i].y+1; k++) if(j!=a[i].x||k!=a[i].y) if(GG[(LL)j*maxn+k]) add_edge(a[i].id,GG[(LL)j*maxn+k]); } for(int i=1; i<=n; i++) if(!dfn[i])tarjan(i); for(int x=1;x<=n;x++) for(int i=head[x];i;i=edge[i].next) if(belong[x]!=belong[edge[i].to]) Add_edge(belong[x],belong[edge[i].to]); for(int i=1;i<=tot;i++) if(!vis[i]) dfs(i); printf("%d\n",ans); return 0;}